package com.template.tree;

import com.template.Random;
import com.template.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author shenb
 * @date 2022-02-26 16:02
 */
public class _3_TreeTraversal {

  /** 前序遍历 */
  public static void preOrder(TreeNode treeNode, List<Integer> integers) {
    if (treeNode == null) {
      return;
    }
    integers.add(treeNode.val);
    preOrder(treeNode.left, integers);
    preOrder(treeNode.right, integers);
  }

  /** 中序遍历 */
  public static void midOrder(TreeNode treeNode, List<Integer> integers) {
    if (treeNode == null) {
      return;
    }
    midOrder(treeNode.left, integers);
    integers.add(treeNode.val);
    midOrder(treeNode.right, integers);
  }

  /** 后序遍历 */
  public static void postOrder(TreeNode treeNode, List<Integer> integers) {
    if (treeNode == null) {
      return;
    }
    postOrder(treeNode.left, integers);
    postOrder(treeNode.right, integers);
    integers.add(treeNode.val);
  }

  /**
   * 深度
   * @param root
   * @return
   */
  public static int getDepth(TreeNode root) {
    if (root == null) {
      return 0;
    }
    return 1 + Math.max(getDepth(root.left), getDepth(root.right));
  }

  public static int count(TreeNode root) {
    if (root == null) {
      return 0;
    }
    return 1 + count(root.left) + count(root.right);
  }

  public static void main(String[] args) {
    TreeNode treeNode = Random.randomTree();
    System.out.println(treeNode);

    System.out.println("前序遍历");
    List<Integer> pre = new ArrayList<>();
    preOrder(treeNode, pre);
    System.out.println(pre);
    System.out.println(_4_TreeTraversal2.preOrder(treeNode));

    System.out.println("中序遍历");
    List<Integer> mid = new ArrayList<>();
    midOrder(treeNode, mid);
    System.out.println(mid);
    System.out.println(_4_TreeTraversal2.midOrder(treeNode));

    System.out.println("后序遍历");
    List<Integer> post = new ArrayList<>();
    postOrder(treeNode, post);
    System.out.println(post);
    System.out.println(_4_TreeTraversal2.postOrder(treeNode));

    System.out.println("广度遍历");
    System.out.println(_5_TreeTraversal3.levelOrder(treeNode));

    System.out.println("深度");
    System.out.println(getDepth(treeNode));

    System.out.println("节点个数");
    System.out.println(count(treeNode));
  }
}
